
// 42.接雨水
class Solution {
public:
    int trap(vector<int>& nums) {
        // 使用两次前缀和
        int n = nums.size();
        // if(n < 3) return 0;
        vector<int> l(n + 1) , r(n + 1);
        for(int i = 1 ; i <= n ; i++)
        {
            l[i] = max(l[i - 1] , nums[i - 1]);
            r[n - i] = max(r[n - i + 1] , nums[n - i]);
        }
        // r[i] 表示i位置的最大高度  , l[i + 1]表示i位置的高度

        int ret = 0;
        for(int i = 0; i < n ; i++)
            ret += min(l[i + 1] , r[i]) - nums[i];
        return ret;
    }
};